package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

/**
 * @Author: waxijiang
 * @Date: 2021/6/2
 * <p>
 * 1. 从中序与后序遍历序列构造二叉树
 * <p>
 * 2。从前序与中序遍历序列构造二叉树
 */
public class BuildTree {
    private static int postRootIndex;

    public static void main(String[] args) {
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        int[] postorder = new int[]{9, 15, 7, 20, 3};
        // 题目1
//        TreeNode treeNode = buildTreeByInorderWithPostorder(inorder, postorder);
        TreeNode treeNode = buildTreeByPreorderWithInorder(preorder, inorder);
        System.out.println(treeNode);
    }

    public static TreeNode buildTreeByInorderWithPostorder(int[] inorder, int[] postorder) {
        postRootIndex = inorder.length - 1;
        return buildTreeByInorderWithPostorderHelper(0, inorder.length, inorder, postorder);
    }

    private static TreeNode buildTreeByInorderWithPostorderHelper(int start, int end, int[] inorder, int[] postorder) {
        if (start == end) {
            return null;
        }

        TreeNode root;
        int rootIndex = 0;
        // 定位根节点
        for (int i = start; i < end; i++) {
            if (postorder[postRootIndex] == inorder[i]) {
                rootIndex = i;
                --postRootIndex;
                break;
            }
        }

        root = new TreeNode(inorder[rootIndex]);
        root.right = buildTreeByInorderWithPostorderHelper(rootIndex + 1, end, inorder, postorder);
        root.left = buildTreeByInorderWithPostorderHelper(start, rootIndex, inorder, postorder);
        return root;
    }

    public static TreeNode buildTreeByPreorderWithInorder(int[] preorder, int[] inorder) {
        postRootIndex = 0;
        return buildTreeByPreorderWithInorderHelper(0, inorder.length, preorder, inorder);
    }

    private static TreeNode buildTreeByPreorderWithInorderHelper(int start, int end, int[] preorder, int[] inorder) {
        if (start == end) {
            return null;
        }

        TreeNode root;
        int rootIndex = 0;
        for (int i = start; i < end; i++) {
            if (inorder[i] == preorder[postRootIndex]) {
                rootIndex = i;
                postRootIndex++;
                break;
            }
        }
        root = new TreeNode(inorder[rootIndex]);
        root.left = buildTreeByPreorderWithInorderHelper(start, rootIndex, preorder, inorder);
        root.right = buildTreeByPreorderWithInorderHelper(rootIndex + 1, end, preorder, inorder);
        return root;
    }

}
